package org.example;

public class Main {
    public static void main(String[] args) {
        System.out.println(kmpSearch("aabaabaaf", "aaf"));//6
        System.out.println(kmpSearch("aabaabaaf", "aab"));//0
        System.out.println(kmpSearch("aabaabaaf", "aaba"));//0
        System.out.println(kmpSearch("aabaabaaf", "aabab"));//-1
    }

    //构建next数组
    //next[i]表示：在模式串的[0, i]区间内，最长公共前后缀的长度
    private static int[] getNext(String pattern){
        int n = pattern.length();
        char[] s = pattern.toCharArray();// 将模式串转为字符数组方便操作
        //初始化next数组
        int[] next = new int[n];

        int j = 0;// j有两个含义：
                    // 1. 指向前缀末尾位置
                    // 2. 表示当前最长公共前后缀的长度

        next[0] = 0; // 单个字符没有前后缀，固定为0

        //// 从索引1开始构建next数组（因为单个字符无需比较）
        for(int i = 1; i < n; i++){
            // 关键逻辑：当字符不匹配时，利用已知的next回退
            // j > 0 保证不越界，s[i] != s[j]表示当前后缀不匹配
            while(j > 0 && s[j] != s[i]){
                j = next[j - 1];// 回退到前一个位置的next值，尝试较短的前缀
            }
            // 如果当前字符匹配，则最长公共前后缀长度+1
            if(s[i] == s[j]){
                j++;// 公共长度+1，同时j也指向下一个前缀位置
            }
            // 记录当前位置的最终结果
            next[i] = j;
        }
        return next;
    }
    //在kmpSearch中使用next函数逻辑
    public static int kmpSearch(String str, String sub){
        if(str == null || sub == null) return -1;
        if(str.length() == 0 || sub.length() == 0) return -1;

        int[] next = getNext(sub);
        int j = 0;//子串指针
        for(int i = 0; i < str.length(); i++){
            //不匹配时回退到前一位的next值
            while(j > 0 && str.charAt(i) != sub.charAt(j)){
                j = next[j - 1];
            }
            if(str.charAt(i) == sub.charAt(j)) j++;
            if(j == sub.length()) return i - j + 1;
        }

        return -1;
    }
}